import java.util.Arrays;
import java.util.TreeMap;

public class Solution31 {
    public void nextPermutation(int[] nums) {
        int maxNum = Integer.MIN_VALUE;
        int repInd = -1;
        for (int i = nums.length - 1; i >= 0; i--) {
            int tmpNum = nums[i];
            if(tmpNum < maxNum){
                repInd = i;
                break;
            }
            else{
                maxNum = tmpNum;
            }
        }

        if(repInd == -1){
            Arrays.sort(nums);
            return;
        }
        int repNum = nums[repInd];
        int minHigherNum = Integer.MAX_VALUE, minHigherInd = -1;
        for (int i = repInd + 1; i < nums.length; i++) {
            int tmpNum = nums[i];
            if(repNum < tmpNum && tmpNum < minHigherNum){
                minHigherNum = tmpNum;
                minHigherInd = i;
            }
        }
        int tmpNum = nums[repInd];
        nums[repInd] = nums[minHigherInd];
        nums[minHigherInd] = tmpNum;
        Arrays.sort(nums, repInd + 1, nums.length);
    }
}
